package 二叉树.从上到下打印二叉树;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/8 17:09
 * @description:剑指offer
 * @version:
 */
public class Solution {
    public static void main(String[] args) {

    }

    //BFS  如果是从上到下遍历二叉树2这道题，那么采用的就是层次遍历
    public static int[] levelOrder(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        List<TreeNode> list = new ArrayList<>();
        if (root == null){
            return new int[]{};
        }
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                TreeNode pop = queue.pop();
                list.add(pop);
                if (pop.left != null){
                    queue.add(pop.left);
                }
                if (pop.right != null){
                    queue.add(pop.right);
                }
                size--;
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i).val;
        }
        return result;
    }
}
